package com.zwxu.list;

public class RemoveNthNode {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		ListNode node1 = new ListNode(1);
		ListNode node2 = new ListNode(2);
		ListNode node3 = new ListNode(3);
		ListNode node4 = new ListNode(4);
		node1.next = node2;
		node2.next = node3;
		node3.next = node4;
		//ListNode temp = node1;
		ListNode temp = removeNthFromEnd(node1,2);
		while(temp != null){
			System.out.print(temp.val+">");
			temp = temp.next;
			
		}

	}
	
	/*
	 * 如果是第一种情况，则需要删除的倒数第N个节点就是头结点，所以head=head.next；删除头结点；
	         如果是第二种情况，则p继续向后挪动，q也紧跟着向后挪动，此时当p向后挪动到链表尾部时停止，
	         此时q指的位置就是该链表的倒数第N个节点，所以q.next=q.next.next;即删除了该节点
	 */
	static ListNode  removeNthFromEnd(ListNode head, int n) {
		ListNode p=head;
	      ListNode q=head;
	        for(int i=0;i<n;i++){
	            p=p.next;
	        }
	        if(p==null){
	            head=head.next;
	            return head;
	        }
	        while(p.next!=null){
	            p=p.next;
	            q=q.next;
	        }
	        q.next=q.next.next;
	        return head;
	    }

}
